#include <stdio.h>
#include <stdlib.h>
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int findIdx(int spells,int *potions,int potionsSize,long long success){
    long target=(success+spells-1)/spells;
    int left=0,right=potionsSize-1,mid;
    while( left <= right ){
        mid=left+((right-left)>>1);
        if( potions[mid] >= target )
            right=mid-1;
        else
            left=mid+1;
    }
    return left;
}
int cmp(const void *a,const void *b){
    int x=*(int*)a,y=*(int*)b;
    if( x>y )return 1;
    else if( x>y )return -1;
    else return 0;
}
int* successfulPairs(int* spells, int spellsSize, int* potions, int potionsSize, long long success, int* returnSize) {
    qsort(potions,potionsSize,sizeof(int),cmp);
    int *ret=malloc(sizeof(int)*spellsSize);
    *returnSize=spellsSize;
    for( int i=0; i<spellsSize; i++ )
        ret[i]=potionsSize-findIdx(spells[i],potions,potionsSize,success);
    return ret;
}


int main(){
    int spells[] = {3,1,2}, potions[] = {8,5,8}, success = 16,rs;
    int *r=successfulPairs(spells,sizeof(spells)/sizeof(int),potions,sizeof(potions)/sizeof(int),success,&rs);
    for(int i=0;i<sizeof(spells)/sizeof(int);i++)
        printf("%d ",r[i]);
    return 0;
}

